/* File: maze_4b.c
 * --------------------
 * Author: Albin Olausson & Stella Wallin
 * Last modified: 2014-04-17
 * Task: A recursive program that compares
 * how many recursive calls are needed 
 * to find a way out from a maze. 
 */

#include <stdio.h>
#include "genlib.h"
#include "graphics.h"
#include "mazelib.h"
#include "simpio.h"

/* Global variables */

static int count1 = 0;
static int count = 0;

/* Private function prototypes */

static bool SolveMazeWithUnmark(pointT pt);
static bool SolveMazeWithoutUnmark(pointT pt);
static pointT AdjacentPoint(pointT pt, directionT dir);

/* Main program */

main()
{	
	string MazeFile;
	SetPauseTime(0.01);
	printf("Program by S. Wallin & A. Olausson.\n\n");
	printf("Input name of maze file: \n");
	MazeFile = GetLine();
    InitGraphics();
    ReadMazeMap(MazeFile);
    if (SolveMazeWithUnmark(GetStartPosition())) {
        printf("%d recursive calls.\n", count1);
    } else {
        printf("No solution exists.\n");
    }
	ReadMazeMap(MazeFile);
	    if (SolveMazeWithoutUnmark(GetStartPosition())) {
        printf("%d recursive calls.\n", count);
    } else {
        printf("No solution exists.\n");
    }
}

/*
 * Function: SolveMazeWithUnmark
 * Usage: if (SolveMazeWithUnmark(pt)) . . 
 * -------------------------------
 * Solves the maze and unmarks the path
 * it used, returns TRUE when it finds a path
 * that leads to an exit.
 */

static bool SolveMazeWithUnmark(pointT pt)
{
    directionT dir;

    if (OutsideMaze(pt))
		return (TRUE);
    if (IsMarked(pt))
		return (FALSE);
    MarkSquare(pt);
    for (dir = North; dir <= West; dir++) {
        if (!WallExists(pt, dir)) {
			count1++;
            if (SolveMazeWithUnmark(AdjacentPoint(pt, dir))) {
                return (TRUE);
            }
        }
    }
    UnmarkSquare(pt);
    return (FALSE);
}

/*
 * Function: SolveMazeWithoutUnmark
 * Usage: if (SolveMazeWithoutUnmark(pt)) . . 
 * -------------------------------
 * Solves the maze and marks the path
 * it used, returns TRUE when it finds a path
 * that leads to an exit.
 */

static bool SolveMazeWithoutUnmark(pointT pt){
	    directionT dir;

    if (OutsideMaze(pt)) return (TRUE);
    if (IsMarked(pt)) return (FALSE);
    MarkSquare(pt);
    for (dir = North; dir <= West; dir++) {
        if (!WallExists(pt, dir)) {
			count++;
            if (SolveMazeWithoutUnmark(AdjacentPoint(pt, dir))) {
                return (TRUE);
            }
        }
    }
    return (FALSE);
}

/*
 * Function: AdjacentPoint
 * Usage: newpt = AdjacentPoint(pt, dir);
 * --------------------------------------
 * This function returns the pointT that results from moving
 * one square from pt in the direction specified by dir.  For
 * example, if pt is the point (1,1), AdjacentPoint(pt, East)
 * would return the point (2,1).
 */

static pointT AdjacentPoint(pointT pt, directionT dir)
{
    pointT newpt;

    newpt = pt;
    switch (dir) {
      case North: newpt.y++; break;
      case East:  newpt.x++; break;
      case South: newpt.y--; break;
      case West:  newpt.x--; break;;
    }
    return (newpt);
}
